package leetcode.code1395;

import leetcode.IDebug;

public class Solution implements IDebug {

	int range = (int) 1e5 + 1;

	public int numTeams(int[] rating) {
		int n = rating.length;
		int ans = 0;
		Record right = new Record(range);
		for (int i = 1; i < n; i++) {
			right.add(rating[i]);
		}
		Record left = new Record(range);
		left.add(rating[0]);
		for (int i = 1; i < n; i++) {
			int num = rating[i];
			right.sub(num);
			ans += left.queryLessThan(num) * right.queryGreaterThan(num);
			ans += left.queryGreaterThan(num) * right.queryLessThan(num);
			left.add(num);
		}
		return ans;
	}

	class Record {
		int len;
		int[] arr;
		int all;

		public Record(int n) {
			len = n + 2;
			arr = new int[len];
		}

		public void add(int num) {
			while (num < len) {
				arr[num]++;
				num += this.lowbit(num);
			}
			all++;
		}

		public void sub(int num) {
			while (num < len) {
				arr[num]--;
				num += this.lowbit(num);
			}
			all--;
		}

		public int query(int num) {
			int ans = 0;
			while (num > 0) {
				ans += arr[num];
				num -= this.lowbit(num);
			}
			return ans;
		}

		public int queryLessThan(int num) {
			return this.query(num - 1);
		}

		public int queryGreaterThan(int num) {
			return all - this.query(num);
		}

		public int lowbit(int num) {
			return num & -num;
		}
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		System.out.println(Integer.toBinaryString(10));
		System.out.println(Integer.toBinaryString(-10));
	}

}
